package com.zjsru.leetcode75.level1.tree;

/**
 * @Author: cookLee
 * @Date: 2023-12-12
 */
public class DeleteNode {
    /**
     * 主
     * \
     * 输入：root = [5,3,6,2,4,null,7], key = 3
     * 输出：[5,4,6,2,null,null,7]
     * 解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
     * 一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
     * 另一个正确答案是 [5,2,6,null,4,null,7]。
     * \
     * 输入: root = [5,3,6,2,4,null,7], key = 0
     * 输出: [5,3,6,2,4,null,7]
     * 解释: 二叉树不包含值为 0 的节点
     * \
     * @param args args
     */
    public static void main(String[] args) {
        TreeNode tree = new TreeNode(5, new TreeNode(3, new TreeNode(2), new TreeNode(4, null, null)), new TreeNode(6, null, new TreeNode(7, null, null)));
        int key = 3;
        DeleteNode deleteNode = new DeleteNode();
        System.out.println(deleteNode.deleteNode(tree,key));
    }

    /**
     * 删除节点
     *
     * @param root 根
     * @param key  钥匙
     * @return {@link TreeNode}
     */
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null){
            return null;
        }
        if(root.val > key){
            root.left = this.deleteNode(root.left,key);
            return root;
        }
        if(root.val < key){
            root.right = this.deleteNode(root.right,key);
            return root;
        }
        //当前节点的值为要删除的值
        if(root.val == key){
            //如果是叶子节点的时候则直接删除
            if (root.left == null && root.right == null) {
                return null;
            }
            //如果只有左子树，将其作为新的子树
            if(root.right == null){
                return root.left;
            }
            //如果只有右子树，同上
            if(root.left == null){
                return root.right;
            }
            //如果左右节点都存在 用它的右子树中的最小节点，记为 success作为新的根节点替代
            TreeNode success = root.right;
            //最小节点
            while (success.left != null) {
                success = success.left;
            }
            //开始删除右节点，并将其值赋给当前节点。
            root.right = this.deleteNode(root.right, success.val);
            //合并左子树和右子树
            success.right = root.right;
            success.left = root.left;
            return success;
        }
        return root;
    }

}
